﻿// -------------------------------------------------------------------------
//    @FileName         :    TestNFShmHashSetWithListSort.h
//    @Author           :    Assistant
//    @Date             :    25-9-25
//    @Email            :    assistant@openai.com
//    @Module           :    TestNFShmHashSetWithListSort
//
// -------------------------------------------------------------------------

#pragma once

#include <gtest/gtest.h>
#include "NFComm/NFShmStl/NFShmHashSetWithList.h"
#include "NFComm/NFShmStl/NFShmHashMultiSetWithList.h"
#include <string>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cmath>
#include <random>
#include <map>
#include <set>

/**
 * @file TestNFShmHashSetWithListSort.h
 * @brief NFShmHashSetWithList和NFShmHashMultiSetWithList的排序功能单元测试
 * 
 * 测试覆盖范围：
 * 1. NFShmHashSetWithList的sort_list()功能测试
 * 2. NFShmHashMultiSetWithList的sort_list()功能测试
 * 3. 各种比较器的测试
 * 4. 复杂对象的排序测试
 * 5. 性能测试
 * 6. 边界情况测试
 */

// ==================== 测试用数据结构 ====================

/**
 * @brief 用于测试复杂对象排序的学生信息结构
 */
struct StudentInfo
{
    int id;
    std::string name;
    int grade;
    double gpa;

    StudentInfo() : id(0), grade(0), gpa(0.0)
    {
    }

    StudentInfo(int i, const std::string& n, int g, double gpa_val) : id(i), name(n), grade(g), gpa(gpa_val)
    {
    }

    bool operator==(const StudentInfo& other) const
    {
        return id == other.id; // 按ID判断相等性
    }

    bool operator<(const StudentInfo& other) const
    {
        return id < other.id; // 默认按ID排序
    }
};

// StudentInfo的哈希函数
namespace std
{
    template <>
    struct hash<StudentInfo>
    {
        size_t operator()(const StudentInfo& s) const
        {
            return std::hash<int>{}(s.id);
        }
    };
}

// ==================== NFShmHashSetWithList 排序测试 ====================

/**
 * @brief 测试NFShmHashSetWithList的基础排序功能
 */
TEST(NFShmHashSetWithListSortTest, BasicSorting)
{
    printf("========== NFShmHashSetWithList BasicSorting Test ==========\n");

    NFShmHashSetWithList<int, 100> intSet;
    intSet.CreateInit();

    // 插入乱序数据
    std::vector<int> test_data = {45, 12, 67, 23, 89, 34, 56, 78, 91, 5};
    for (int val : test_data)
    {
        intSet.insert(val);
    }

    printf("Original insertion order:\n");
    for (auto it = intSet.list_begin(); it != intSet.list_end(); ++it)
    {
        printf("%d ", *it);
    }
    printf("\n");

    // 测试默认升序排序
    intSet.sort_list();

    printf("After sort_list() (ascending):\n");
    std::vector<int> sorted_result;
    for (auto it = intSet.list_begin(); it != intSet.list_end(); ++it)
    {
        printf("%d ", *it);
        sorted_result.push_back(*it);
    }
    printf("\n");

    // 验证排序结果
    EXPECT_TRUE(std::is_sorted(sorted_result.begin(), sorted_result.end()));

    // 测试降序排序
    intSet.sort_list(std::greater<int>());

    printf("After sort_list(greater) (descending):\n");
    std::vector<int> desc_result;
    for (auto it = intSet.list_begin(); it != intSet.list_end(); ++it)
    {
        printf("%d ", *it);
        desc_result.push_back(*it);
    }
    printf("\n");

    // 验证降序排序结果
    EXPECT_TRUE(std::is_sorted(desc_result.begin(), desc_result.end(), std::greater<int>()));

    // 验证集合功能仍然正常
    EXPECT_EQ(intSet.size(), test_data.size());
    for (int val : test_data)
    {
        EXPECT_EQ(intSet.count(val), 1);
    }

    printf("NFShmHashSetWithList BasicSorting test passed\n");
}

/**
 * @brief 测试NFShmHashSetWithList的自定义比较器排序
 */
TEST(NFShmHashSetWithListSortTest, CustomComparator)
{
    printf("========== NFShmHashSetWithList CustomComparator Test ==========\n");

    NFShmHashSetWithList<int, 100> numberSet;
    numberSet.CreateInit();

    // 插入包含正负数的数据
    std::vector<int> test_data = {-15, 23, -8, 31, -42, 5, 17, -6, 29};
    for (int val : test_data)
    {
        numberSet.insert(val);
    }

    printf("Original data:\n");
    for (auto it = numberSet.list_begin(); it != numberSet.list_end(); ++it)
    {
        printf("%d ", *it);
    }
    printf("\n");

    // 测试按绝对值排序
    numberSet.sort_list([](const int& a, const int& b)
    {
        return std::abs(a) < std::abs(b);
    });

    printf("After sorting by absolute value:\n");
    std::vector<int> abs_values;
    for (auto it = numberSet.list_begin(); it != numberSet.list_end(); ++it)
    {
        printf("%d (abs:%d) ", *it, std::abs(*it));
        abs_values.push_back(std::abs(*it));
    }
    printf("\n");

    // 验证按绝对值排序
    EXPECT_TRUE(std::is_sorted(abs_values.begin(), abs_values.end()));

    // 测试按奇偶性排序（偶数在前，奇数在后）
    numberSet.sort_list([](const int& a, const int& b)
    {
        if ((a % 2) != (b % 2))
        {
            return (a % 2) == 0; // 偶数优先
        }
        return a < b; // 同奇偶性按大小排序
    });

    printf("After sorting by even/odd (even first):\n");
    bool even_section = true;
    int prev_val = INT_MIN;
    bool is_correctly_sorted = true;

    for (auto it = numberSet.list_begin(); it != numberSet.list_end(); ++it)
    {
        printf("%d ", *it);

        if (even_section && (*it % 2) != 0)
        {
            even_section = false; // 进入奇数区域
        }
        else if (!even_section && (*it % 2) == 0)
        {
            is_correctly_sorted = false; // 奇数区域出现偶数，错误
        }

        // 在同一区域内应该按升序排列
        if (prev_val != INT_MIN && (prev_val % 2) == (*it % 2) && prev_val > *it)
        {
            is_correctly_sorted = false;
        }
        prev_val = *it;
    }
    printf("\n");

    EXPECT_TRUE(is_correctly_sorted);

    printf("NFShmHashSetWithList CustomComparator test passed\n");
}

/**
 * @brief 测试NFShmHashSetWithList的复杂对象排序
 */
TEST(NFShmHashSetWithListSortTest, ComplexObjectSorting)
{
    printf("========== NFShmHashSetWithList ComplexObjectSorting Test ==========\n");

    NFShmHashSetWithList<StudentInfo, 100> studentSet;
    studentSet.CreateInit();

    // 插入学生数据
    std::vector<StudentInfo> students = {StudentInfo(1001, "Alice", 10, 3.8), StudentInfo(1002, "Bob", 11, 3.6), StudentInfo(1003, "Charlie", 10, 3.9), StudentInfo(1004, "David", 12, 3.7), StudentInfo(1005, "Eve", 11, 3.95), StudentInfo(1006, "Frank", 10, 3.5)};

    for (const auto& student : students)
    {
        studentSet.insert(student);
    }

    printf("Original student data:\n");
    for (auto it = studentSet.list_begin(); it != studentSet.list_end(); ++it)
    {
        printf("  ID:%d %s Grade:%d GPA:%.2f\n", it->id, it->name.c_str(), it->grade, it->gpa);
    }

    // 测试按GPA降序排序
    studentSet.sort_list([](const StudentInfo& a, const StudentInfo& b)
    {
        return a.gpa > b.gpa; // 降序
    });

    printf("\nAfter sorting by GPA (descending):\n");
    std::vector<double> gpas;
    for (auto it = studentSet.list_begin(); it != studentSet.list_end(); ++it)
    {
        printf("  ID:%d %s Grade:%d GPA:%.2f\n", it->id, it->name.c_str(), it->grade, it->gpa);
        gpas.push_back(it->gpa);
    }

    EXPECT_TRUE(std::is_sorted(gpas.begin(), gpas.end(), std::greater<double>()));

    // 测试复合排序：先按年级，再按GPA
    studentSet.sort_list([](const StudentInfo& a, const StudentInfo& b)
    {
        if (a.grade != b.grade)
        {
            return a.grade < b.grade;
        }
        return a.gpa > b.gpa; // 同年级按GPA降序
    });

    printf("\nAfter sorting by grade then GPA:\n");
    int prev_grade = 0;
    double prev_gpa = 5.0;
    bool is_correctly_sorted = true;

    for (auto it = studentSet.list_begin(); it != studentSet.list_end(); ++it)
    {
        printf("  ID:%d %s Grade:%d GPA:%.2f\n", it->id, it->name.c_str(), it->grade, it->gpa);

        if (prev_grade != 0)
        {
            if (it->grade < prev_grade || (it->grade == prev_grade && it->gpa > prev_gpa))
            {
                is_correctly_sorted = false;
            }
        }
        prev_grade = it->grade;
        prev_gpa = (it->grade == prev_grade) ? it->gpa : 5.0;
    }

    EXPECT_TRUE(is_correctly_sorted);

    printf("NFShmHashSetWithList ComplexObjectSorting test passed\n");
}

// ==================== NFShmHashMultiSetWithList 排序测试 ====================

/**
 * @brief 测试NFShmHashMultiSetWithList的基础排序功能
 */
TEST(NFShmHashMultiSetWithListSortTest, BasicSorting)
{
    printf("========== NFShmHashMultiSetWithList BasicSorting Test ==========\n");

    NFShmHashMultiSetWithList<int, 100> multiSet;
    multiSet.CreateInit();

    // 插入重复数据
    std::vector<int> test_data = {45, 12, 45, 23, 12, 34, 23, 78, 45, 5, 12};
    for (int val : test_data)
    {
        multiSet.insert(val);
    }

    printf("Original insertion order:\n");
    for (auto it = multiSet.list_begin(); it != multiSet.list_end(); ++it)
    {
        printf("%d ", *it);
    }
    printf("\n");

    EXPECT_EQ(multiSet.size(), test_data.size());
    EXPECT_EQ(multiSet.count(45), 3);
    EXPECT_EQ(multiSet.count(12), 3);
    EXPECT_EQ(multiSet.count(23), 2);

    // 测试升序排序
    multiSet.sort_list();

    printf("After sort_list() (ascending):\n");
    std::vector<int> sorted_result;
    for (auto it = multiSet.list_begin(); it != multiSet.list_end(); ++it)
    {
        printf("%d ", *it);
        sorted_result.push_back(*it);
    }
    printf("\n");

    // 验证排序结果
    EXPECT_TRUE(std::is_sorted(sorted_result.begin(), sorted_result.end()));

    // 验证重复元素都存在
    EXPECT_EQ(multiSet.count(45), 3);
    EXPECT_EQ(multiSet.count(12), 3);
    EXPECT_EQ(multiSet.count(23), 2);

    // 测试降序排序
    multiSet.sort_list(std::greater<int>());

    printf("After sort_list(greater) (descending):\n");
    std::vector<int> desc_result;
    for (auto it = multiSet.list_begin(); it != multiSet.list_end(); ++it)
    {
        printf("%d ", *it);
        desc_result.push_back(*it);
    }
    printf("\n");

    // 验证降序排序结果
    EXPECT_TRUE(std::is_sorted(desc_result.begin(), desc_result.end(), std::greater<int>()));

    printf("NFShmHashMultiSetWithList BasicSorting test passed\n");
}

/**
 * @brief 测试NFShmHashMultiSetWithList的重复元素处理
 */
TEST(NFShmHashMultiSetWithListSortTest, DuplicateHandling)
{
    printf("========== NFShmHashMultiSetWithList DuplicateHandling Test ==========\n");

    NFShmHashMultiSetWithList<std::string, 100> wordSet;
    wordSet.CreateInit();

    // 插入重复的字符串
    std::vector<std::string> words = {"apple", "banana", "apple", "cherry", "banana", "apple", "date", "banana", "elderberry", "apple"};

    for (const auto& word : words)
    {
        wordSet.insert(word);
    }

    printf("Original words:\n");
    for (auto it = wordSet.list_begin(); it != wordSet.list_end(); ++it)
    {
        printf("%s ", it->c_str());
    }
    printf("\n");

    // 统计每个单词的数量
    EXPECT_EQ(wordSet.count("apple"), 4);
    EXPECT_EQ(wordSet.count("banana"), 3);
    EXPECT_EQ(wordSet.count("cherry"), 1);
    EXPECT_EQ(wordSet.count("date"), 1);
    EXPECT_EQ(wordSet.count("elderberry"), 1);

    // 按字母顺序排序
    wordSet.sort_list();

    printf("After alphabetical sorting:\n");
    std::vector<std::string> sorted_words;
    for (auto it = wordSet.list_begin(); it != wordSet.list_end(); ++it)
    {
        printf("%s ", it->c_str());
        sorted_words.push_back(*it);
    }
    printf("\n");

    // 验证排序结果
    EXPECT_TRUE(std::is_sorted(sorted_words.begin(), sorted_words.end()));

    // 验证重复元素仍然存在
    EXPECT_EQ(wordSet.count("apple"), 4);
    EXPECT_EQ(wordSet.count("banana"), 3);

    // 测试按长度排序
    wordSet.sort_list([](const std::string& a, const std::string& b)
    {
        if (a.length() != b.length())
        {
            return a.length() < b.length();
        }
        return a < b; // 长度相同按字母顺序
    });

    printf("After sorting by length then alphabetically:\n");
    size_t prev_length = 0;
    std::string prev_word = "";
    bool is_correctly_sorted = true;

    for (auto it = wordSet.list_begin(); it != wordSet.list_end(); ++it)
    {
        printf("%s(%zu) ", it->c_str(), it->length());

        if (prev_length != 0)
        {
            if (it->length() < prev_length || (it->length() == prev_length && *it < prev_word))
            {
                is_correctly_sorted = false;
            }
        }
        prev_length = it->length();
        prev_word = (it->length() == prev_length) ? *it : "";
    }
    printf("\n");

    EXPECT_TRUE(is_correctly_sorted);

    printf("NFShmHashMultiSetWithList DuplicateHandling test passed\n");
}

/**
 * @brief 性能对比测试
 */
TEST(NFShmHashSetWithListSortTest, PerformanceComparison)
{
    printf("========== PerformanceComparison Test ==========\n");

    constexpr int TEST_SIZE = 1000;

    // 测试NFShmHashSetWithList性能
    {
        NFShmHashSetWithList<int, TEST_SIZE + 100> setContainer;
        setContainer.CreateInit();

        // 插入随机数据
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(1, 10000);

        for (int i = 0; i < TEST_SIZE; ++i)
        {
            setContainer.insert(dis(gen));
        }

        auto start = std::chrono::high_resolution_clock::now();
        setContainer.sort_list();
        auto end = std::chrono::high_resolution_clock::now();
        auto set_sort_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("NFShmHashSetWithList (%d unique elements) sort took %lld microseconds\n", (int)setContainer.size(), set_sort_time.count());

        // 验证排序正确性
        std::vector<int> set_values;
        for (auto it = setContainer.list_begin(); it != setContainer.list_end(); ++it)
        {
            set_values.push_back(*it);
        }
        EXPECT_TRUE(std::is_sorted(set_values.begin(), set_values.end()));
    }

    // 测试NFShmHashMultiSetWithList性能
    {
        NFShmHashMultiSetWithList<int, TEST_SIZE + 100> multisetContainer;
        multisetContainer.CreateInit();

        // 插入数据（包含重复）
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(1, TEST_SIZE / 2); // 产生更多重复

        for (int i = 0; i < TEST_SIZE; ++i)
        {
            multisetContainer.insert(dis(gen));
        }

        auto start = std::chrono::high_resolution_clock::now();
        multisetContainer.sort_list();
        auto end = std::chrono::high_resolution_clock::now();
        auto multiset_sort_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("NFShmHashMultiSetWithList (%d total elements) sort took %lld microseconds\n", (int)multisetContainer.size(), multiset_sort_time.count());

        // 验证排序正确性
        std::vector<int> multiset_values;
        for (auto it = multisetContainer.list_begin(); it != multisetContainer.list_end(); ++it)
        {
            multiset_values.push_back(*it);
        }
        EXPECT_TRUE(std::is_sorted(multiset_values.begin(), multiset_values.end()));
    }

    printf("PerformanceComparison test passed\n");
}

/**
 * @brief 边界情况测试
 */
TEST(NFShmHashSetWithListSortTest, EdgeCases)
{
    printf("========== EdgeCases Test ==========\n");

    // 测试1：空容器
    printf("Test 1: Empty containers\n");
    {
        NFShmHashSetWithList<int, 10> emptySet;
        emptySet.CreateInit();
        emptySet.sort_list();
        EXPECT_EQ(emptySet.size(), 0);

        NFShmHashMultiSetWithList<int, 10> emptyMultiSet;
        emptyMultiSet.CreateInit();
        emptyMultiSet.sort_list();
        EXPECT_EQ(emptyMultiSet.size(), 0);

        printf("Empty containers test passed\n");
    }

    // 测试2：单元素
    printf("Test 2: Single element\n");
    {
        NFShmHashSetWithList<int, 10> singleSet;
        singleSet.CreateInit();
        singleSet.insert(42);
        singleSet.sort_list();
        EXPECT_EQ(singleSet.size(), 1);
        EXPECT_EQ(*singleSet.list_begin(), 42);

        NFShmHashMultiSetWithList<int, 10> singleMultiSet;
        singleMultiSet.CreateInit();
        singleMultiSet.insert(42);
        singleMultiSet.sort_list();
        EXPECT_EQ(singleMultiSet.size(), 1);
        EXPECT_EQ(*singleMultiSet.list_begin(), 42);

        printf("Single element test passed\n");
    }

    // 测试3：所有元素相同（仅MultiSet适用）
    printf("Test 3: All same elements (MultiSet only)\n");
    {
        NFShmHashMultiSetWithList<int, 10> sameMultiSet;
        sameMultiSet.CreateInit();

        for (int i = 0; i < 5; ++i)
        {
            sameMultiSet.insert(100);
        }

        sameMultiSet.sort_list();
        EXPECT_EQ(sameMultiSet.size(), 5);
        EXPECT_EQ(sameMultiSet.count(100), 5);

        for (auto it = sameMultiSet.list_begin(); it != sameMultiSet.list_end(); ++it)
        {
            EXPECT_EQ(*it, 100);
        }

        printf("All same elements test passed\n");
    }

    printf("EdgeCases test passed\n");
}

// ==================== NFShmHashMultiSetWithList 专门测试 ====================

/**
 * @brief 专门测试NFShmHashMultiSetWithList的复杂排序场景
 */
TEST(NFShmHashMultiSetWithListSortTest, ComplexMultiSetSorting)
{
    printf("========== ComplexMultiSetSorting Test ==========\n");

    NFShmHashMultiSetWithList<StudentInfo, 100> studentMultiSet;
    studentMultiSet.CreateInit();

    // 插入重复学生数据（模拟转学、重复记录等场景）
    std::vector<StudentInfo> students = {
        StudentInfo(1001, "Alice", 10, 3.8), StudentInfo(1001, "Alice", 10, 3.8), // 重复记录
        StudentInfo(1002, "Bob", 11, 3.6), StudentInfo(1003, "Charlie", 10, 3.9), StudentInfo(1002, "Bob", 11, 3.7), // 同一学生但GPA不同（更新记录）
        StudentInfo(1004, "David", 12, 3.7), StudentInfo(1005, "Eve", 11, 3.95), StudentInfo(1003, "Charlie", 10, 3.9), // 重复记录
    };

    for (const auto& student : students)
    {
        studentMultiSet.insert(student);
    }

    printf("Original student data (%d records):\n", (int)studentMultiSet.size());
    for (auto it = studentMultiSet.list_begin(); it != studentMultiSet.list_end(); ++it)
    {
        printf("  ID:%d %s Grade:%d GPA:%.2f\n", it->id, it->name.c_str(), it->grade, it->gpa);
    }

    EXPECT_EQ(studentMultiSet.size(), students.size());
    EXPECT_EQ(studentMultiSet.count(StudentInfo(1001, "Alice", 10, 3.8)), 2);
    EXPECT_EQ(studentMultiSet.count(StudentInfo(1002, "Bob", 11, 3.6)), 2);
    EXPECT_EQ(studentMultiSet.count(StudentInfo(1002, "Bob", 11, 3.7)), 2);

    // 测试1：按GPA降序排序
    studentMultiSet.sort_list([](const StudentInfo& a, const StudentInfo& b)
    {
        return a.gpa > b.gpa; // 降序
    });

    printf("\nAfter sorting by GPA (descending):\n");
    std::vector<double> gpas;
    for (auto it = studentMultiSet.list_begin(); it != studentMultiSet.list_end(); ++it)
    {
        printf("  ID:%d %s Grade:%d GPA:%.2f\n", it->id, it->name.c_str(), it->grade, it->gpa);
        gpas.push_back(it->gpa);
    }

    EXPECT_TRUE(std::is_sorted(gpas.begin(), gpas.end(), std::greater<double>()));

    // 测试2：复合排序：先按年级，再按GPA降序，最后按ID
    studentMultiSet.sort_list([](const StudentInfo& a, const StudentInfo& b)
    {
        if (a.grade != b.grade)
        {
            return a.grade < b.grade;
        }
        if (a.gpa != b.gpa)
        {
            return a.gpa > b.gpa; // 同年级按GPA降序
        }
        return a.id < b.id; // 同GPA按ID升序
    });

    printf("\nAfter sorting by grade, then GPA(desc), then ID:\n");
    int prev_grade = 0;
    double prev_gpa = 5.0;
    int prev_id = 0;
    bool is_correctly_sorted = true;

    for (auto it = studentMultiSet.list_begin(); it != studentMultiSet.list_end(); ++it)
    {
        printf("  ID:%d %s Grade:%d GPA:%.2f\n", it->id, it->name.c_str(), it->grade, it->gpa);

        if (prev_grade != 0)
        {
            // 检查排序逻辑：
            // 1. 年级应该递增，或者
            // 2. 同年级内GPA应该递减，或者  
            // 3. 同年级同GPA内ID应该递增
            bool valid_order = (it->grade > prev_grade) || (it->grade == prev_grade && it->gpa < prev_gpa) || (it->grade == prev_grade && it->gpa == prev_gpa && it->id >= prev_id);
            if (!valid_order)
            {
                is_correctly_sorted = false;
                printf("  *** Sort order violation detected: current(Grade:%d GPA:%.2f ID:%d) vs prev(Grade:%d GPA:%.2f ID:%d) ***\n", it->grade, it->gpa, it->id, prev_grade, prev_gpa, prev_id);
            }
        }

        // 更新前一个记录的值
        prev_grade = it->grade;
        prev_gpa = it->gpa;
        prev_id = it->id;
    }

    EXPECT_TRUE(is_correctly_sorted);

    printf("ComplexMultiSetSorting test passed\n");
}

/**
 * @brief 测试NFShmHashMultiSetWithList的重复元素分组排序
 */
TEST(NFShmHashMultiSetWithListSortTest, DuplicateGroupSorting)
{
    printf("========== DuplicateGroupSorting Test ==========\n");

    NFShmHashMultiSetWithList<std::string, 100> tagMultiSet;
    tagMultiSet.CreateInit();

    // 模拟标签系统，插入大量重复标签
    std::vector<std::pair<std::string, int>> tags_with_counts = {{"VIP", 5}, {"Premium", 3}, {"Basic", 8}, {"Trial", 2}, {"Premium", 4}, {"VIP", 3}, {"Enterprise", 1}, {"Basic", 2}};

    for (const auto& tag_info : tags_with_counts)
    {
        for (int i = 0; i < tag_info.second; ++i)
        {
            tagMultiSet.insert(tag_info.first);
        }
    }

    printf("Original tag distribution:\n");
    std::map<std::string, int> tag_counts;
    for (auto it = tagMultiSet.list_begin(); it != tagMultiSet.list_end(); ++it)
    {
        tag_counts[*it]++;
    }

    for (std::map<std::string, int>::const_iterator it = tag_counts.begin(); it != tag_counts.end(); ++it)
    {
        printf("  %s: %d times\n", it->first.c_str(), it->second);
    }

    printf("Total tags: %d\n", (int)tagMultiSet.size());
    EXPECT_EQ(tagMultiSet.count("VIP"), 8);
    EXPECT_EQ(tagMultiSet.count("Premium"), 7);
    EXPECT_EQ(tagMultiSet.count("Basic"), 10);
    EXPECT_EQ(tagMultiSet.count("Trial"), 2);
    EXPECT_EQ(tagMultiSet.count("Enterprise"), 1);

    // 按字典序排序
    tagMultiSet.sort_list();

    printf("\nAfter alphabetical sorting:\n");
    std::vector<std::string> sorted_tags;
    for (auto it = tagMultiSet.list_begin(); it != tagMultiSet.list_end(); ++it)
    {
        sorted_tags.push_back(*it);
    }

    // 验证排序结果
    EXPECT_TRUE(std::is_sorted(sorted_tags.begin(), sorted_tags.end()));

    // 验证相同标签聚集在一起
    std::string current_tag = "";
    bool in_group = false;
    std::map<std::string, int> grouped_counts;

    for (const auto& tag : sorted_tags)
    {
        if (tag != current_tag)
        {
            if (in_group)
            {
                printf("  %s group ended\n", current_tag.c_str());
            }
            current_tag = tag;
            in_group = true;
            printf("  %s group started\n", current_tag.c_str());
        }
        grouped_counts[tag]++;
    }

    // 验证分组计数正确
    EXPECT_EQ(grouped_counts["VIP"], 8);
    EXPECT_EQ(grouped_counts["Premium"], 7);
    EXPECT_EQ(grouped_counts["Basic"], 10);
    EXPECT_EQ(grouped_counts["Trial"], 2);
    EXPECT_EQ(grouped_counts["Enterprise"], 1);

    printf("DuplicateGroupSorting test passed\n");
}

/**
 * @brief 测试NFShmHashMultiSetWithList的大规模数据性能
 */
TEST(NFShmHashMultiSetWithListSortTest, LargeScaleMultiSetPerformance)
{
    printf("========== LargeScaleMultiSetPerformance Test ==========\n");

    constexpr int UNIQUE_VALUES = 200;
    constexpr int DUPLICATES_PER_VALUE = 5;
    constexpr int TOTAL_SIZE = UNIQUE_VALUES * DUPLICATES_PER_VALUE;

    NFShmHashMultiSetWithList<int, TOTAL_SIZE + 100> largeMultiSet;
    largeMultiSet.CreateInit();

    // 生成测试数据：每个值重复多次
    std::vector<int> test_values;
    for (int val = 1; val <= UNIQUE_VALUES; ++val)
    {
        for (int dup = 0; dup < DUPLICATES_PER_VALUE; ++dup)
        {
            test_values.push_back(val);
        }
    }

    // 随机打乱插入顺序
    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_values.begin(), test_values.end(), gen);

    // 插入数据
    for (int val : test_values)
    {
        largeMultiSet.insert(val);
    }

    printf("Performance test with %d elements (%d unique values, %d duplicates each):\n", TOTAL_SIZE, UNIQUE_VALUES, DUPLICATES_PER_VALUE);

    EXPECT_EQ(largeMultiSet.size(), TOTAL_SIZE);

    // 验证重复计数
    for (int val = 1; val <= UNIQUE_VALUES; ++val)
    {
        EXPECT_EQ(largeMultiSet.count(val), DUPLICATES_PER_VALUE);
    }

    // 测试排序性能
    auto start = std::chrono::high_resolution_clock::now();
    largeMultiSet.sort_list();
    auto end = std::chrono::high_resolution_clock::now();
    auto sort_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    printf("sort_list() took %lld microseconds\n", sort_time.count());

    // 验证排序正确性
    std::vector<int> sorted_values;
    for (auto it = largeMultiSet.list_begin(); it != largeMultiSet.list_end(); ++it)
    {
        sorted_values.push_back(*it);
    }
    EXPECT_TRUE(std::is_sorted(sorted_values.begin(), sorted_values.end()));

    // 验证每组重复元素的连续性
    int current_value = 0;
    int current_count = 0;
    std::map<int, int> value_counts;

    for (int val : sorted_values)
    {
        if (val != current_value)
        {
            if (current_value != 0)
            {
                value_counts[current_value] = current_count;
                printf("Value %d appears %d times consecutively\n", current_value, current_count);
            }
            current_value = val;
            current_count = 1;
        }
        else
        {
            current_count++;
        }
    }
    // 处理最后一组
    if (current_value != 0)
    {
        value_counts[current_value] = current_count;
        printf("Value %d appears %d times consecutively\n", current_value, current_count);
    }

    // 验证每个值的计数
    for (std::map<int, int>::const_iterator it = value_counts.begin(); it != value_counts.end(); ++it)
    {
        EXPECT_EQ(it->second, DUPLICATES_PER_VALUE);
    }

    EXPECT_EQ(value_counts.size(), UNIQUE_VALUES);

    printf("LargeScaleMultiSetPerformance test passed\n");
}

/**
 * @brief 测试NFShmHashMultiSetWithList的特殊排序需求
 */
TEST(NFShmHashMultiSetWithListSortTest, SpecialSortingRequirements)
{
    printf("========== SpecialSortingRequirements Test ==========\n");

    NFShmHashMultiSetWithList<int, 100> specialMultiSet;
    specialMultiSet.CreateInit();

    // 插入测试数据，包含各种类型的数字
    std::vector<int> test_data = {15, -10, 33, 0, -7, 22, 15, -10, 8, 33, 0, -7, 100, -50, 45, 15, 0, -10, 77, 22, -7, 33};

    for (int val : test_data)
    {
        specialMultiSet.insert(val);
    }

    printf("Original data with duplicates:\n");
    std::map<int, int> original_counts;
    for (auto it = specialMultiSet.list_begin(); it != specialMultiSet.list_end(); ++it)
    {
        original_counts[*it]++;
    }

    for (std::map<int, int>::const_iterator it = original_counts.begin(); it != original_counts.end(); ++it)
    {
        printf("  %d appears %d times\n", it->first, it->second);
    }

    // 测试1：按绝对值排序，但保持重复元素
    specialMultiSet.sort_list([](const int& a, const int& b)
    {
        if (std::abs(a) != std::abs(b))
        {
            return std::abs(a) < std::abs(b);
        }
        return a < b; // 绝对值相同时，负数在前
    });

    printf("\nAfter sorting by absolute value (negative first for same abs):\n");
    std::vector<int> abs_sorted;
    for (auto it = specialMultiSet.list_begin(); it != specialMultiSet.list_end(); ++it)
    {
        printf("%d ", *it);
        abs_sorted.push_back(*it);
    }
    printf("\n");

    // 验证绝对值排序正确性
    for (size_t i = 1; i < abs_sorted.size(); ++i)
    {
        int prev_abs = std::abs(abs_sorted[i - 1]);
        int curr_abs = std::abs(abs_sorted[i]);

        EXPECT_TRUE(prev_abs <= curr_abs) << "Absolute value ordering violated at position " << i;

        if (prev_abs == curr_abs)
        {
            EXPECT_TRUE(abs_sorted[i-1] <= abs_sorted[i]) << "Same absolute value ordering violated at position " << i;
        }
    }

    // 测试2：按奇偶性分组排序
    specialMultiSet.sort_list([](const int& a, const int& b)
    {
        bool a_even = (a % 2 == 0);
        bool b_even = (b % 2 == 0);

        if (a_even != b_even)
        {
            return a_even; // 偶数在前
        }
        return a < b; // 同奇偶性按大小排序
    });

    printf("\nAfter sorting by even/odd (even first, then ascending within group):\n");
    std::vector<int> parity_sorted;
    bool in_even_section = true;

    for (auto it = specialMultiSet.list_begin(); it != specialMultiSet.list_end(); ++it)
    {
        printf("%d ", *it);
        parity_sorted.push_back(*it);

        if (in_even_section && (*it % 2 != 0))
        {
            in_even_section = false;
            printf("| "); // 标记奇偶分界
        }
    }
    printf("\n");

    // 验证奇偶性排序
    bool found_odd = false;
    int prev_even = INT_MIN, prev_odd = INT_MIN;

    for (int val : parity_sorted)
    {
        if (val % 2 == 0)
        {
            EXPECT_FALSE(found_odd) << "Found even number after odd numbers: " << val;
            EXPECT_TRUE(val >= prev_even) << "Even numbers not in ascending order";
            prev_even = val;
        }
        else
        {
            found_odd = true;
            EXPECT_TRUE(val >= prev_odd) << "Odd numbers not in ascending order";
            prev_odd = val;
        }
    }

    // 验证重复元素计数保持不变
    std::map<int, int> final_counts;
    for (auto it = specialMultiSet.list_begin(); it != specialMultiSet.list_end(); ++it)
    {
        final_counts[*it]++;
    }

    EXPECT_EQ(original_counts, final_counts) << "Element counts changed after sorting";

    printf("SpecialSortingRequirements test passed\n");
}

/**
 * @brief 测试NFShmHashMultiSetWithList与NFShmHashSetWithList的行为差异
 */
TEST(NFShmHashMultiSetWithListSortTest, SetVsMultiSetComparison)
{
    printf("========== SetVsMultiSetComparison Test ==========\n");

    NFShmHashSetWithList<int, 50> uniqueSet;
    NFShmHashMultiSetWithList<int, 50> multiSet;

    uniqueSet.CreateInit();
    multiSet.CreateInit();

    // 插入相同的数据到两个容器
    std::vector<int> test_data = {5, 3, 8, 3, 1, 5, 9, 1, 3, 7, 5, 2};

    for (int val : test_data)
    {
        uniqueSet.insert(val);
        multiSet.insert(val);
    }

    printf("Original data: ");
    for (int val : test_data)
    {
        printf("%d ", val);
    }
    printf("\n");

    printf("Set size: %d, MultiSet size: %d\n", (int)uniqueSet.size(), (int)multiSet.size());

    // 验证容器大小差异
    EXPECT_LT(uniqueSet.size(), multiSet.size()) << "Set should have fewer elements than MultiSet";
    EXPECT_EQ(multiSet.size(), test_data.size()) << "MultiSet should contain all inserted elements";

    // 验证重复计数
    EXPECT_EQ(uniqueSet.count(3), 1) << "Set should have exactly 1 of each element";
    EXPECT_EQ(multiSet.count(3), 3) << "MultiSet should have all duplicate elements";
    EXPECT_EQ(uniqueSet.count(5), 1);
    EXPECT_EQ(multiSet.count(5), 3);
    EXPECT_EQ(uniqueSet.count(1), 1);
    EXPECT_EQ(multiSet.count(1), 2);

    // 排序两个容器
    uniqueSet.sort_list();
    multiSet.sort_list();

    printf("\nAfter sorting:\n");
    printf("Set contents: ");
    std::vector<int> set_contents;
    for (auto it = uniqueSet.list_begin(); it != uniqueSet.list_end(); ++it)
    {
        printf("%d ", *it);
        set_contents.push_back(*it);
    }
    printf("\n");

    printf("MultiSet contents: ");
    std::vector<int> multiset_contents;
    for (auto it = multiSet.list_begin(); it != multiSet.list_end(); ++it)
    {
        printf("%d ", *it);
        multiset_contents.push_back(*it);
    }
    printf("\n");

    // 验证排序结果
    EXPECT_TRUE(std::is_sorted(set_contents.begin(), set_contents.end()));
    EXPECT_TRUE(std::is_sorted(multiset_contents.begin(), multiset_contents.end()));

    // 验证去重效果
    std::set<int> unique_values(test_data.begin(), test_data.end());
    std::vector<int> expected_unique(unique_values.begin(), unique_values.end());

    EXPECT_EQ(set_contents, expected_unique) << "Set should contain only unique sorted elements";

    // 验证MultiSet包含所有重复元素
    std::vector<int> expected_multi = test_data;
    std::sort(expected_multi.begin(), expected_multi.end());

    EXPECT_EQ(multiset_contents, expected_multi) << "MultiSet should contain all elements sorted";

    printf("SetVsMultiSetComparison test passed\n");
}
